package com.bee.剑指offer;

import java.util.ArrayList;

/**
 * 最小的K个数
 *
 * @version 1.0.0
 * @Author yong.Mr
 * @data 2021-04-30
 */
public class 最小的K个数 {

    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (k > input.length || k <= 0 || input.length == 0) {
            return result;
        }
        quickSort(input, 0, input.length - 1);
        for (int i = 0; i < k; i++) {
            result.add(input[i]);
        }
        return result;
    }

    public static void quickSort(int[] input, int left, int right) {
        if (left > right) {
            return;
        }
        int base = input[left];
        int low = left;
        int high = right;
        while (low != high) {
            // 先从右到左检索，找比base小的数，停下来
            while (input[high] >= base && low < high) {
                high--;
            }
            // 先从左到右检索，找比base大的数，停下来
            while (input[low] <= base && low < high) {
                low++;
            }
            int temp = input[low];
            input[low] = input[high];
            input[high] = temp;
        }
        input[left] = input[low];
        input[low] = base;
        quickSort(input, left, low - 1);
        quickSort(input, low + 1, right);
    }


    public static void main(String[] args) {
        ArrayList<Integer> integers = GetLeastNumbers_Solution(new int[]{4, 5, 1, 6, 2, 7, 2, 8}, 2);
        System.out.println(integers);
    }
}
